// SearchSubString.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <Windows.h>
#include <vector>
#include <iostream>
using namespace std;
void calcF(TCHAR const* pattern, int* F)
{

    for(int i = 0, j =0; pattern[i]; ++i,++j)
    {
        while(j>0 && pattern[j-1]!=pattern[i]) 
        {
            j = F[j-1];
        }
        F[i] = j;
        _tprintf_s(L"%d   ", F[i]);
    }


}

void GetNextPosTable(LPCTSTR pStrPattern, vector<int> & refNextTable)
{
    if (NULL == pStrPattern)
    {
        _tprintf_s(L"The Pattern string is null!\n");    
        return;
    }

    size_t nLen = _tcslen(pStrPattern);
    refNextTable.resize(nLen);

    refNextTable[0] = -1; 
    int j = 0;
    for (size_t i = 1; i<nLen; i++)
    {
        if (pStrPattern[i] == pStrPattern[j])
        {

            refNextTable[i] = j;
            j ++;
        }
        else
        {
            refNextTable[i] = j;
            j = 0;
        }
    }
}

void PrintfOutNextTable(const vector<int> nextTable)
{
    for (size_t i = 0; i< nextTable.size(); i++)
    {
        _tprintf_s(L"%d ", nextTable[i]);
    }
    _tprintf_s(L"\n");
}

wstring GetInputLine(LPCTSTR lpDirectMessage)
{
    if (NULL != lpDirectMessage)
    {
        _tprintf_s(L"%s\n", lpDirectMessage);
    }
    else
    {
        _tprintf_s(L"Please input test string \n");
    }

START:
    wstring strInput;
    TCHAR ch = getchar();
    while(ch !='\n')
    {
        strInput.push_back(ch);
        ch = getchar();
    }
    if (strInput.size() == 0)
    {
        _tprintf_s(L"You must input something!\n");
        goto START;
    }

    return strInput;
}
bool Search(const wstring strSource, const wstring strPattern, int & nPos)
{
    bool bFound = false;
    int nSourceLen = (int)strSource.size();
    int nPatternLen = (int)strPattern.size();
    vector<int> vectNextTable;
    GetNextPosTable(strPattern.c_str(), vectNextTable);
    PrintfOutNextTable(vectNextTable);

    int i = 0; int j = 0;
    while(i< nSourceLen && j< nPatternLen)
    {
        if (strSource[i] == strPattern[j])
        {
            j++;
            i++;
        }
        else
        {
            if (j == 0)
            {
                i++;
                continue;
            }

            j = vectNextTable[j];
            
        }
      
    }

    if (j == nPatternLen  && i <= nSourceLen)
    {
        bFound = true;
        nPos = i - nPatternLen; 
    }
    return bFound;
}

int _tmain(int argc, _TCHAR* argv[])
{
    do 
    {
        int nPos = -1;
        wstring strSource = GetInputLine(L"Please input the source string");
        if (strSource.compare(L"exit") == 0)
        {
            return 0;
        }

        wstring strPattern = GetInputLine(L"Please input string you want to find");
        if (strPattern.compare(L"exit") == 0)
        {
            return 0;
        }
        
        
        bool bRet = Search(strSource, strPattern,  nPos);

        if (bRet)
        {
            _tprintf_s(L"Found %s in \n%s \nAt %d\n", strPattern.c_str(), strSource.c_str(), nPos);
        }
        else
        {
            _tprintf_s(L"Can' t find %s in \n%s\n", strPattern.c_str(), strSource.c_str());
        }      
    }
    while(true);


    return 0;
}

